package code_capriccio;

import java.util.*;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


// 代码随想录（二叉树章节）
@SuppressWarnings({"all"})
public class Demo10 {


    // 144. 二叉树的前序遍历（非递归）
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;

        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()) {
            if(root != null) {
                ret.add(root.val);
                stack.push(root);
                root = root.left;
            } else {
                TreeNode top = stack.pop();
                root = top.right;
            }
        }
        return ret;
    }


    // 94. 二叉树的中序遍历（非递归）
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;

        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()) {
            if(root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode top = stack.pop();
                ret.add(top.val);
                root = top.right;
            }
        }
        return ret;
    }



    //145. 二叉树的后序遍历（非递归）
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while(root != null || !stack.isEmpty()) {
            if(root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode tmp = stack.peek();
                if(tmp.right == null || prev == tmp.right) {
                    TreeNode top = stack.pop();
                    ret.add(top.val);
                    prev = top;
                } else {
                    root = tmp.right;
                }
            }
        }
        return ret;
    }



    //102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()) {
            int sz = q.size();
            List<Integer> tmp = new ArrayList<>();
            while(sz-- > 0) {
                TreeNode node = q.poll();
                tmp.add(node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            ret.add(tmp);
        }
        return ret;
    }



    //LCR 144. 翻转二叉树
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        TreeNode leftTree = root.left;      // 先保存左子树或右子树，防止下面的操作出现错误
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(leftTree);
        return root;
    }



    //101. 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        return childIsSymmetric(root.left, root.right);
    }
    public boolean childIsSymmetric(TreeNode leftTree, TreeNode rightTree) {
        if(leftTree == null && rightTree == null) return true;
        if(leftTree == null || rightTree == null) return false;

        if(leftTree.val != rightTree.val) return false;
        return childIsSymmetric(leftTree.left, rightTree.right) && childIsSymmetric(leftTree.right, rightTree.left);
    }



    //104. 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }


    //111. 二叉树的最小深度
    public int minDepth(TreeNode root) {
        if(root == null) return 0;

        int lH = minDepth(root.left);
        int rH = minDepth(root.right);

        if(lH != 0 && rH != 0) return Math.min(lH, rH) + 1;
        if(lH != 0) return lH + 1;
        return rH + 1;
    }



    //222. 完全二叉树的节点个数
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }


    //110. 平衡二叉树
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    private int getHeight(TreeNode root) {
        if(root == null) return 0;

        int lH = getHeight(root.left);
        if(lH == -1) return -1;
        int rH = getHeight(root.right);
        if(rH == -1) return -1;
        return Math.abs(lH - rH) <= 1 ? Math.max(lH, rH) + 1 : -1;
    }


    //257. 二叉树的所有路径
    List<String> ret;
    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        dfs(root, new StringBuilder());
        return ret;
    }
    private void dfs(TreeNode root, StringBuilder _path) {
        StringBuilder path = new StringBuilder(_path);
        path.append(Integer.toString(root.val));
        if(root.left == null && root.right == null) {
            ret.add(path.toString());
            return;
        }

        path.append("->");
        if(root.left != null) dfs(root.left, path);
        if(root.right != null) dfs(root.right, path);
    }


    //404. 左叶子之和
    int count;      // 用来标记是否是根结点
    public int sumOfLeftLeaves(TreeNode root) {
        count++;
        if (root == null) return 0;
        if (root.left == null && root.right == null) {  // 叶子节点则返回值
            if (count == 1) return 0;
            return root.val;
        }

        int ret = sumOfLeftLeaves(root.left);   // 左子树所有左叶子的值之和
        if (root.right != null) {                // 右子树不为空，修改右结点的值作为判断依据
            root.right.val = -1001;
            int rightValue = sumOfLeftLeaves(root.right);
            ret += rightValue == -1001 ? 0 : rightValue;    // 右子树存在左叶子结点则相加
        }
        return ret;
    }




    //LCR 045. 找树左下角的值
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        int ret = 0;
        while(!q.isEmpty()) {
            int sz = q.size();
            ret = q.peek().val;
            while(sz-- > 0) {
                TreeNode f = q.poll();
                if(f.left != null) q.offer(f.left);
                if(f.right != null) q.offer(f.right);
            }
        }
        return ret;
    }



    //112. 路径总和
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        targetSum -= root.val;
        if(root.left == null && root.right == null && targetSum == 0) return true;

        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
    }



    //437. 路径总和 III
    int count2 = 0;
    public int pathSum(TreeNode root, int targetSum) {  //对所有结点进行一次 dfs遍历
        if(root == null) return 0;
        dfs(root, (long)targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return count;
    }
    // 从每个结点开始进行深搜，计算从该结点到所有孩子结点 路径上节点值之和等于 target的路径数目
    public void dfs(TreeNode root, long targetSum) {
        if(root == null) return;
        targetSum -= root.val;
        if(targetSum == 0) count2++;
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
    }




    //106. 从中序与后序遍历序列构造二叉树
    int pos;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pos = inorder.length - 1;
        return forgeTree(inorder, postorder, 0, inorder.length - 1);
    }
    public TreeNode forgeTree(int[] inorder, int[] postorder, int left, int right) {
        if(left > right) return null;
        TreeNode root = new TreeNode(postorder[pos--]);
        int index = searchIndex(inorder, left, right, root.val);

        root.right = forgeTree(inorder, postorder, index + 1, right);
        root.left = forgeTree(inorder,postorder, left, index - 1);
        return root;
    }
    public int searchIndex(int[] inorder, int left, int right, int val) {
        while(left <= right) {
            if(inorder[left] == val) return left;
            left++;
        }
        return 0;
    }





    //654. 最大二叉树
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }
    public TreeNode buildTree(int[] nums, int left, int right) {
        if(left > right) return null;

        int index = searchIndex(nums, left, right);
        TreeNode root = new TreeNode(nums[index]);
        root.left = buildTree(nums, left, index - 1);
        root.right = buildTree(nums, index + 1, right);
        return root;
    }
    public int searchIndex(int[] nums, int left, int right) {
        int max = left;
        while(left <= right) {
            if(nums[left] > nums[max]) max = left;
            left++;
        }
        return max;
    }




    //617. 合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return null;
        if(root1 != null && root2 == null) return root1;
        if(root1 == null && root2 != null) return root2;

        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }




    //700. 二叉搜索树中的搜索
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null) return null;
        if(root.val == val) return root;
        if(root.val < val) return searchBST(root.right, val);
        return searchBST(root.left, val);
    }




    //98. 验证二叉搜索树
    TreeNode prev = null;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;

        if(!isValidBST(root.left)) return false;
        if(prev != null && prev.val >= root.val) return false;
        prev = root;
        return isValidBST(root.right);
    }




    //530. 二叉搜索树的最小绝对差
    int ret4 = 100001, val = -1;
    public int getMinimumDifference(TreeNode root) {
        if(root == null) return 0;
        getMinimumDifference(root.left);
        if(val != -1) ret4 = Math.min(ret4, Math.abs(val - root.val));
        val = root.val;
        getMinimumDifference(root.right);
        return ret4;
    }


    //501. 二叉搜索树中的众数
    TreeNode prev3;
    int count3, maxCount3 = 1;
    List<Integer> ret3;

    public int[] findMode(TreeNode root) {
        ret3 = new ArrayList<>();
        inorder(root);
        int[] answer = new int[ret3.size()];
        for(int i = 0; i < ret3.size(); i++) answer[i] = ret3.get(i);
        return answer;
    }

    private void inorder(TreeNode cur) {
        if(cur == null) return;

        inorder(cur.left);
        if(prev == null || prev.val != cur.val) {
            count = 1;
        } else {
            count++;
        }
        if(count > maxCount3) {
            ret3.clear();
            maxCount3++;
        }
        if(count == maxCount3) ret3.add(cur.val);
        prev = cur;
        inorder(cur.right);
    }





    //LCR 194. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode lTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rTree = lowestCommonAncestor(root.right, p, q);
        if(lTree != null && rTree != null) return root;
        if(lTree != null) return lTree;
        return rTree;
    }




    //LCR 193. 二叉搜索树的最近公共祖先
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q || (root.val - p.val) * (root.val - q.val) < 0) return root;

        if(root.val < p.val) return lowestCommonAncestor2(root.right, p, q);
        return lowestCommonAncestor2(root.left, p, q);
    }




    //701. 二叉搜索树中的插入操作
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);

        if(root.val > val) root.left = insertIntoBST(root.left, val);
        else root.right = insertIntoBST(root.right, val);
        return root;
    }




    //450. 删除二叉搜索树中的节点
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        //寻找值的为key的结点， 并用该结点右子树的最左边的结点替换
        if(root.val == key) {
            TreeNode tmp = searchNode(root.right);
            if(tmp == null) return root.left;       // 如果没有右子树，返回左子树的根结点
            tmp.left = root.left;
            if(root.right != tmp) tmp.right = root.right;   // 若存在右子树最左边的结点，则改变结点的连接关系
            return tmp;
        }

        TreeNode prev = root, cur = root;
        while(cur != null) {
            if(cur.val == key) {
                TreeNode tmp = searchNode(cur.right);
                if(tmp == null) {                   // 要删除的结点没有右子树，直接让 prev的后序结点连接 cur的left
                    if(prev.left == cur) prev.left = cur.left;
                    else prev.right = cur.left;
                } else {                            // 要删除结点存在右子树，返回的tmp为 cur的右结点或右子树的最左边结点
                    if(prev.left == cur) prev.left = tmp;   // 处理 prev和tmp的连接关系
                    else prev.right = tmp;
                    tmp.left = cur.left;
                    if(tmp != cur.right) {                  // 若 tmp 为右子树最左边的结点，则让tmp的右结点连接cur的右结点
                        tmp.right = cur.right;
                    }
                }
                break;
            } else {        // 找到结点值 == key 的结点
                prev = cur;
                if(cur.val > key) {
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }
            }
        }
        return root;
    }
    // 返回要删除结点右子树最左边的结点，并处理返回结点的连接关系
    private TreeNode searchNode(TreeNode root) {
        if(root == null || root.left == null) return root;

        TreeNode prev = root, cur = root.left;
        while(cur.left != null) {
            prev = cur;
            cur = cur.left;
        }
        prev.left = cur.right;
        return cur;
    }





    //669. 修剪二叉搜索树
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return null;
        if(root.val < low) return trimBST(root.right, low, high);   // 结点值在范围之外，则返回对应范围内的情况
        if(root.val > high) return trimBST(root.left, low, high);

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }




    //108. 将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        return convertBBSTree(nums, 0, nums.length - 1);
    }
    public TreeNode convertBBSTree(int[] nums, int left, int right) {
        if(left > right) return null;

        int mid = (left + right) / 2;       // 每次取范围内的中点，将左右子树结点数量平均分配
        TreeNode root = new TreeNode(nums[mid]);
        root.left = convertBBSTree(nums, left, mid - 1);
        root.right = convertBBSTree(nums, mid + 1, right);
        return root;
    }




    //LCR 054. 把二叉搜索树转换为累加树
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null) return null;       // 中序遍历：右中左
        convertBST(root.right);
        root.val = (sum += root.val);
        convertBST(root.left);
        return root;
    }




//    public static void main(String[] args) {
//        leetcode.TreeNode node2 = new leetcode.TreeNode(2);
//        leetcode.TreeNode node3 = new leetcode.TreeNode(3);
//        leetcode.TreeNode node4 = new leetcode.TreeNode(4);
//        leetcode.TreeNode node5 = new leetcode.TreeNode(5);
//        leetcode.TreeNode node6 = new leetcode.TreeNode(6);
//        leetcode.TreeNode node7 = new leetcode.TreeNode(7);
//        node5.left = node3;
//        node3.left = node2;
//        node3.right = node4;
//        node5.right = node6;
//        node6.right = node7;
//        convertBST(node5);
//    }


    public static void main(String[] args) {
        //ret3 = combinationSum3(new int[]{2,5,2,1,2}, 5);
    }


}
